package collection;

import java.util.Comparator;
import java.util.Iterator;

import exception.CollectionEmptyException;

public class HeapPriorityQueue<K, V> implements IPriorityQueue<K, V> {

	private ArrayCompleteBinTree<Entry<K,V>> heap;
	private Comparator<K> comp;
	
	public HeapPriorityQueue(Comparator<K> comp)
	{
		this.heap = new ArrayCompleteBinTree<Entry<K,V>>();
		this.comp = comp;
	}
	
	@Override
	public int size() 
	{
		return this.heap.size();
	}

	@Override
	public boolean isEmpty() 
	{
		return this.heap.isEmpty();
	}

	@Override
	public Entry<K, V> min() throws CollectionEmptyException 
	{
		if (isEmpty())
			throw new CollectionEmptyException("Priority Queue");
		else
			return heap.getRoot().getElement();
	}

	@Override
	public Entry<K,V> insert(K key, V value) 
	{
		Entry<K,V> newEntry = new Entry<K,V>(key, value);
		heap.addElement(newEntry);
		upHeap(heap.getLastNode());
		
		return newEntry;
	}

	@Override
	public Entry<K, V> removeMin() throws CollectionEmptyException 
	{
		if (isEmpty())
			throw new CollectionEmptyException("Priority Queue");
		else
		{
			Entry<K,V> retEntry = heap.getRoot().getElement();
			if (heap.size() == 1)
			{
				heap.removeLast();
			}
			else if (heap.size() > 1)
			{
				heap.getRoot().setElement(heap.getLastElement());
				heap.removeLast();
				downHeap(heap.getRoot());
			}
			
			return retEntry;
		}
	}
	
	public void upHeap(BinTreeNodeWithIndex<Entry<K,V>> someNode)
	{
		BinTreeNodeWithIndex<Entry<K,V>> currentNode = someNode;
		BinTreeNodeWithIndex<Entry<K,V>> parentNode = heap.getParent(someNode);
		while(parentNode!= null && comp.compare(currentNode.getElement().getKey(), parentNode.getElement().getKey()) < 0)
		{
			Entry<K,V> tempEntry = currentNode.getElement();
			currentNode.setElement(parentNode.getElement());
			parentNode.setElement(tempEntry);
			
			currentNode = parentNode;
			parentNode = heap.getParent(currentNode);
		}
	}
	
	private BinTreeNodeWithIndex<Entry<K,V>> getChildNodeForDownHeap(BinTreeNodeWithIndex<Entry<K,V>> someNode)
	{
		BinTreeNodeWithIndex<Entry<K,V>> leftChild = heap.getLeftChild(someNode);
		BinTreeNodeWithIndex<Entry<K,V>> rightChild = heap.getRightChild(someNode);
		
		if (leftChild == null && rightChild == null)
		{
			return null;
		}
		else if (leftChild !=null && rightChild != null)
		{
			if (comp.compare(leftChild.getElement().getKey(), rightChild.getElement().getKey())<=0)
			{
				return leftChild;
			}
			else
			{
				return rightChild;
			}
		}
		else if (leftChild == null)
		{
			return rightChild;
		}
		else
		{
			return leftChild;
		}
	}
	
	public void downHeap(BinTreeNodeWithIndex<Entry<K,V>> someNode)
	{
		BinTreeNodeWithIndex<Entry<K,V>> currentNode = someNode;
		BinTreeNodeWithIndex<Entry<K,V>> childNode = getChildNodeForDownHeap(someNode);
		
		while(childNode!= null && comp.compare(currentNode.getElement().getKey(), childNode.getElement().getKey()) > 0)
		{
			Entry<K,V> tempEntry = currentNode.getElement();
			currentNode.setElement(childNode.getElement());
			childNode.setElement(tempEntry);
			
			currentNode = childNode;
			childNode = getChildNodeForDownHeap(currentNode);
		}
	}

	@Override
	public Iterator<Entry<K, V>> iterator() 
	{
		SLinkedList<Entry<K,V>> entryList = new SLinkedList<Entry<K,V>>();
		while(!heap.isEmpty())
		{
			entryList.addLast(entryList.createNode(removeMin()));
		}
		
		// restore the heap
		this.heap = new ArrayCompleteBinTree<Entry<K,V>>();
		for (SNode<Entry<K,V>> entryNode : entryList)
		{
			Entry<K,V> entry = entryNode.getElement();
			insert(entry.getKey(), entry.getValue());
		}
		
		return entryList.elementsIterator();
	}

}
